Курсова Робота
На тему:
Створення ігрової програми "шашки" для гри між людиною і комп'ютером на мові С + + Builder
1. Базові поняття ШІ .. 4
2. Історія розвитку систем ІІ .. 8
Різні підходи до побудови систем ШІ .. 16
Скорочений лістинг програми і опис алгоритму. 21
компоненти штучного інтелекту (ІІ) 26
Опис роботи програми .. 37
Висновки .. 39
Література. 40
Тому, в теоретичну частину винесені основні відомості про розробку алгоритмів ШІ, показана історична лінія розвитку завдань ШІ.
Для створення гри "шашки" потрібно відносно нескладна функція ШІ, головними завданнями якої є передбачення на встановлену глибину своїх ходів і ходів противника. Це пророцтво базується на виборі найкращих ходів з обох сторін. На фінальному етапі функція ШІ обирає найбільш вигідну для комп'ютера ланцюжок ходів.
Термінологія.
Термін інтелект (intelligence) походить від латинського intellectus - що означає розум, розум, розум; розумові здібності людини. Відповідно штучний інтелект (artificial intelligence) - ШІ (AI) звичайно тлумачиться як властивість автоматичних систем брати на себе окремі функції інтелекту людини, наприклад, вибирати і приймати оптимальні рішення на основі раніше отриманого досвіду і раціонального аналізу зовнішніх впливів.
Ми, в нашому курсі, інтелектом будемо називати здатність мозку вирішувати (інтелектуальні) задачі шляхом придбання, запам'ятовування і цілеспрямованого перетворення знань в процесі навчання на досвіді й адаптації до різноманітних обставин.
У цьому визначенні під терміном "знання" мається на увазі не тільки ту інформацію, яка надходить у мозок через органи почуттів. Такого типу знання надзвичайно важливі, але недостатні для інтелектуальної діяльності. Справа в тому, що об'єкти навколишньої середовища мають властивість не тільки впливати на органи почуттів, але і знаходитися один з одним в певних відносинах. Ясно, що для того, щоб здійснювати в навколишньому середовищі інтелектуальну діяльність (або хоча б просто існувати), необхідно мати в системі знань модель цього світу. У цій інформаційній моделі навколишнього середовища реальні об'єкти, їх властивості і відносини між ними не тільки відображаються і запам'ятовуються, а й, як це зазначено в даному визначенні інтелекту, можуть подумки "цілеспрямовано перетворюватися". При цьому істотно те, що формування моделі зовнішнього середовища відбувається "у процесі навчання на досвіді й адаптації до різноманітних обставин".
Ми вжили термін інтелектуальна задача. Для того, щоб пояснити, чим відрізняється інтелектуальна завдання від просто завдання, необхідно ввести термін "алгоритм" - один з наріжних термінів кібернетики.
Під алгоритмом розуміють точне розпорядження про виконання в певному порядку системи операцій для вирішення будь-якої задачі з деякого даного класу (безлічі) завдань. Термін "алгоритм" походить від імені узбецького математика Аль-Хорезмі, який ще в IX столітті запропонував найпростіші арифметичні алгоритми. У математиці та кібернетиці клас задач певного типу вважається вирішеним, коли для її рішення встановлений алгоритм. Знаходження алгоритмів є природною метою людини при вирішенні ним різноманітних класів задач. Відшукування алгоритму для задач деякого даного типу пов'язане з тонкими і складними міркуваннями, які вимагають великої винахідливості і високої кваліфікації. Прийнято вважати, що подібного роду діяльність вимагає участі інтелекту людини. Завдання, пов'язані з віднайденням алгоритму розв'язання класу задач певного типу, будемо називати інтелектуальними.
Що ж стосується завдань, алгоритми вирішення яких вже встановлені, то, як зазначає відомий фахівець у галузі ШІ М. Мінський, "надмірно приписувати їм таке містичне властивості, як" інтелектуальність ". Справді, після того, як такий алгоритм уже знайдений, процес розв'язання відповідних задач стає таким, що його можуть у точності виконати людина, обчислювальна машина (належним чином запрограмована) або робот, що не мають ні найменшого уявлення про сутність самої задачі. Потрібно тільки, щоб особа, що вирішує завдання, була здатна виконувати ті елементарні операції , з яких складається процес, і, крім того, щоб воно педантично і акуратно керувалося запропонованим алгоритмом. Така особа, діючи, як кажуть у таких випадках, чисто машинально, може успішно вирішувати будь-яке завдання аналізованого типу.
Тому видається цілком природним виключити їх класу інтелектуальних такі завдання, для яких існують стандартні методи рішення. Прикладами таких задач можуть служити чисто обчислювальні задачі: рішення системи лінійних алгебраїчних рівнянь, чисельне інтегрування диференціальних рівнянь і т.д. Для вирішення подібного роду завдань є стандартні алгоритми, що представляють собою певну послідовність елементарних операцій, яка може бути легко реалізована у вигляді програми для обчислювальної машини. На противагу цьому для широкого класу інтелектуальних завдань, таких, як розпізнавання образів, гра в шахи, доведення теорем і т.п., навпаки це формальне розбивка процесу пошуку рішення на окремі елементарні кроки часто виявляється дуже складною, навіть якщо сама їх рішення нескладно.
Таким чином, ми можемо перефразувати визначення інтелекту як універсальний сверхалгорітм, який здатний створювати алгоритми вирішення конкретних завдань.
Ще цікавим зауваженням тут є те, що професія програміста, виходячи з наших визначень, є однією з найбільш інтелектуальних, оскільки продуктом діяльності програміста є програми - алгоритми в чистому вигляді. Саме тому, створення навіть елементів ШІ має дуже сильно підвищити продуктивність його праці.
Діяльність мозку (володіє інтелектом), спрямовану на вирішення інтелектуальних завдань, ми будемо називати мисленням, або інтелектуальною діяльністю. Інтелект і мислення органічно пов'язані з вирішенням таких завдань, як доказ теорем, логічний аналіз, розпізнавання ситуацій, планування поведінки, ігри та управління в умовах невизначеності. Характерними рисами інтелекту, що проявляються в процесі вирішення завдань, є здатність до навчання, узагальнення, накопичення досвіду (знань і навичок) і адаптації до умов, що змінюються в процесі вирішення завдань. Завдяки цим якостям інтелекту мозок може вирішувати різноманітні завдання, а також легко перебудовуватися з рішення однієї задачі на іншу. Таким чином, мозок, наділений інтелектом, є універсальним засобом вирішення широкого кола завдань (в тому числі неформалізованих) для яких немає стандартних, заздалегідь відомих методів рішення.
Слід мати на увазі, що існують і інші, чисто поведінкові (функціональні) визначення. Так, за А.Н. Колмогорова, будь-яка матеріальна система, з якою можна досить довго обговорювати проблеми науки, літератури і мистецтва, володіє інтелектом. Іншим прикладом поведінкової трактування інтелекту може слугувати відоме визначення А. Тьюринга. Його сенс полягає в наступному. У різних кімнатах знаходиться люди і машина. Вони не можуть бачити одне одного, але мають можливість обмінюватися інформацією (наприклад, за допомогою електронної пошти). Якщо в процесі діалогу між учасниками гри людям не вдається встановити, що один з учасників - машина, то таку машину можна вважати володіє інтелектом.
До речі цікавий план імітації мислення, запропонований А. Тьюрінгом. "Намагаючись імітувати інтелект дорослої людини, - пише Тьюринг, - ми змушені багато розмірковувати про той процес, в результаті якого людський мозок досяг свого справжнього стану ... Чому б нам замість того, щоб намагатися створити програму, яка імітує інтелект дорослої людини, не спробувати створити програму , яка імітувала б інтелект дитини? Адже якщо інтелект дитини отримує відповідне виховання, він стає інтелектом дорослої людини ... Наш розрахунок полягає в тому, що пристрій, йому подібне, може бути легко запрограмоване ... Таким чином, ми розчленуємо нашу проблему на дві частини: на завдання побудови "програми-дитини" і завдання "виховання" цієї програми ".
Забігаючи наперед, можна сказати, що саме цей шлях використовують практично всі системи ШІ. Адже зрозуміло, що практично неможливо закласти всі знання в досить складну систему. Крім того, тільки на цьому шляху виявляться перераховані вище ознаки інтелектуальної діяльності (накопичення досвіду, адаптація тощо).
У рамках першого підходу об'єктом досліджень є структура і механізми роботи мозку людини, а кінцева мета полягає в розкритті таємниць мислення. Необхідними етапами досліджень у цьому напрямку є побудова моделей на основі психофізіологічних даних, проведення експериментів з ними, висування нових гіпотез щодо механізмів інтелектуальної діяльності, удосконалення моделей і т.д.
Другий підхід в якості об'єкта дослідження розглядає ШІ. Тут мова йде про моделювання інтелектуальної діяльності за допомогою обчислювальних машин. Метою робіт у цьому напрямку є створення алгоритмічного і програмного забезпечення обчислювальних машин, що дозволяє вирішувати інтелектуальні задачі не гірше людини.
Нарешті, третій підхід орієнтований на створення змішаних людино-машинних, або, як ще кажуть, інтерактивних інтелектуальних систем, на симбіоз можливостей природного і штучного інтелекту. Найважливішими проблемами в цих дослідженнях є оптимальний розподіл функцій між природним і штучним інтелектом і організація діалогу між людиною і машиною.
Найпершими інтелектуальними завданнями, які стали вирішуватися за допомогою ЕОМ були логічні ігри (шашки, шахи), доказ теорем. Хоча, правда тут треба відзначити ще кібернетичні іграшки типу "електронної миші" Клода Шеннона, що керувалася складної релейного схемою. Ця мишка могла "дослідити" лабіринт, і знаходити вихід з нього. А крім того, вміщена у вже відомий їй лабіринт, вона не шукала вихід, а відразу ж, не заглядаючи в тупикові ходи, виходила з лабіринту.
Американський кібернетик А. Самуель склав для обчислювальної машини програму, яка дозволяє їй грати в шашки, причому в ході гри машина навчається або, принаймні, створює враження, що навчається, покращуючи свою гру на основі накопиченого досвіду. У 1962 р. ця програма зіграли з Р. Нілі, найсильнішим шашкістом в США і перемогла.
Яким чином машині вдалося досягти такого високого класу гри?
Природно, що в машину були програмно закладені правила гри так, що вибір чергового ходу був підпорядкований цими правилами. На кожній стадії гри машина вибирала черговий хід з безлічі можливих ходів відповідно до певного критерію якості гри. У шашках (як і в шахах) зазвичай невигідно втрачати свої фігури, і, навпаки, вигідно брати фігури супротивника. Гравець (будь він людина чи машина), який зберігає рухливість своїх фігур і право вибору ходів і в той же час тримає під боєм велике число полів на дошці, зазвичай грає краще за свого супротивника, не додає значення цих елементів гри. Описані критерії хорошої гри зберігають свою силу протягом всієї гри, але є й інші критерії, які відносяться до окремих її стадіях - дебюту, міттендшпілю, ендшпілю.
Розумно поєднуючи такі критерії (наприклад, у вигляді лінійної комбінації з експериментально бираються коефіцієнтами або більш складним чином), можна для оцінки чергового ходу машини отримати деякий числовий показник ефективності - оціночну функцію. Тоді машина, порівнявши між собою показники ефективності чергових ходів, вибере хід, відповідний найбільшому показнику. Подібна автоматизація вибору чергового ходу не обов'язково забезпечує оптимальний вибір, але все ж це якийсь вибір, і на його основі машина може продовжувати гру, удосконалюючи свою стратегію (образ дії) в процесі навчання на минулому досвіді. Формально навчання полягає в підстроюванні параметрів (коефіцієнтів) оцінної функції на основі аналізу проведених ходів та ігор з урахуванням їх результату.
На думку А. Самуеля, машина, яка використовує цей вид навчання, може навчитися грати краще, ніж середній гравець, за відносно короткий період часу.
Можна сказати, що всі ці елементи інтелекту, продемонстровані машиною в процесі гри в шашки, повідомлені їй автором програми. Частково це так. Але не слід забувати, що програма ця не є "жорсткою", заздалегідь продуманої у всіх деталях. Вона удосконалює свою стратегію гри в процесі самонавчання. І хоча процес "мислення" у машини істотно різниться від того, що відбувається в мозку грає в шашки людини, вона здатна у нього виграти.
Яскравим прикладом складної інтелектуальної гри до недавнього часу були шахи. У 1974 р. відбувся міжнародний шаховий турнір машин, забезпечених відповідними програмами. Як відомо, перемогу на цьому турнірі здобула радянська машина з шаховою програмою "Каїсса".
Чому тут вжито "до недавнього часу"? Справа в тому, що недавні події показали, що незважаючи на досить велику складність шахів, і неможливість, у зв'язку з цим зробити повний перебір ходів, можливість перебору їх на велику глибину, ніж зазвичай, дуже збільшує шанси на перемогу. Наприклад, за повідомленнями у пресі, комп'ютер фірми IBM, який переміг Каспарова, мав 256 процесорів, кожний з яких мав 4 Гб дискової пам'яті і 128 Мб оперативної. Весь цей комплекс міг прораховувати більш 100'000'000 ходів у секунду. До недавнього часу рідкістю був комп'ютер, який може робити таку кількість цілочисельних операцій в секунду, а тут ми говоримо про ходах, які повинні бути генеровані і для яких прораховані оціночні функції. Хоча з іншого боку, цей приклад свідчить про могутність і універсальності переборних алгоритмів.
В даний час існують і успішно застосовуються програми, що дозволяють машинам грати у ділові або військові ігри, що мають велике прикладне значення. Тут також надзвичайно важливо надати програмами властиві людині здатність до навчання та адаптації. Однією з найбільш цікавих інтелектуальних завдань, також має величезне прикладне значення, є задача навчання розпізнавання образів і ситуацій. Рішенням її займалися і продовжують займатися представники різних наук - фізіологи, психологи, математики, інженери. Такий інтерес до задачі стимулювався фантастичними перспективами широкого практичного використання результатів теоретичних досліджень: читають автомати, системи штучного інтелекту, що ставлять медичні діагнози, які проводять криміналістичну експертизу і т.п., а також роботи, здатні розпізнавати й аналізувати складні сенсорні ситуації.
У 1957 р. американський фізіолог Ф. Розенблатт запропонував модель зорового сприйняття і розпізнавання - перцептрон. Поява машини, здатної навчатися поняттям і розпізнавати запропоновані об'єкти, виявилося надзвичайно цікавим не тільки фізіологам, але і представникам інших областей знання і породило великий потік теоретичних і експериментальних досліджень.
Перцептрон або будь-яка програма, що імітує процес розпізнавання, працюють в двох режимах: в режимі навчання і в режимі розпізнавання. У режимі навчання хтось (людина, машина, робот або природа), що грає роль учителя, пред'являє машині об'єкти та про кожного з них повідомляє, до якого поняття (класу) він належить. За цими даними будується вирішальне правило, що є, по суті, формальним описом понять. У режимі розпізнавання машині пред'являються нові об'єкти (взагалі кажучи, відмінні від раніше пред'явлених), і вона повинна їх класифікувати, по можливості, правильно.
Проблема адаптації розпізнавання тісно пов'язана з іншої інтелектуальної задачею - проблемою перекладу з однієї мови на іншу, а також навчання машини мови. При досить формальної обробці і класифікації основних граматичних правил і прийомів користування словником можна створити цілком задовільний алгоритм для перекладу, скажімо наукового або ділового тексту. Для деяких мов такі системи були створені ще в кінці 60-р. Однак для того, щоб складно перевести досить великий розмовний текст, необхідно розуміти його зміст. Роботи над такими програмами ведуться вже давно, але до повного успіху ще далеко. Є також програми, що забезпечують діалог між людиною і машиною на урізаному природною мовою. На тему:
Створення ігрової програми "шашки" для гри між людиною і комп'ютером на мові С + + Builder
Зміст
Введення. 31. Базові поняття ШІ .. 4
2. Історія розвитку систем ІІ .. 8
Різні підходи до побудови систем ШІ .. 16
Скорочений лістинг програми і опис алгоритму. 21
компоненти штучного інтелекту (ІІ) 26
Опис роботи програми .. 37
Висновки .. 39
Література. 40
Введення
Основою даної роботи є створення ігрової програми "шашки" для гри між людиною і комп'ютером. Для створення "думаючих" ігор потрібно написання головного двигуна гри - функції штучного інтелекту.Тому, в теоретичну частину винесені основні відомості про розробку алгоритмів ШІ, показана історична лінія розвитку завдань ШІ.
Для створення гри "шашки" потрібно відносно нескладна функція ШІ, головними завданнями якої є передбачення на встановлену глибину своїх ходів і ходів противника. Це пророцтво базується на виборі найкращих ходів з обох сторін. На фінальному етапі функція ШІ обирає найбільш вигідну для комп'ютера ланцюжок ходів.
1. Базові поняття ШІ
У сучасному світі прогрес продуктивності програміста практично досягається тільки в тих випадках, коли частина інтелектуального навантаження беруть на себе комп'ютери. Одним із способів досягти максимального прогресу в цій області, є "штучний інтелект", коли комп'ютер бере на себе не тільки однотипні, багаторазово повторювані операції, але й сам зможе навчатися. Крім того, створення повноцінного "штучного інтелекту" відкриває перед людством нові горизонти розвитку.Термінологія.
Термін інтелект (intelligence) походить від латинського intellectus - що означає розум, розум, розум; розумові здібності людини. Відповідно штучний інтелект (artificial intelligence) - ШІ (AI) звичайно тлумачиться як властивість автоматичних систем брати на себе окремі функції інтелекту людини, наприклад, вибирати і приймати оптимальні рішення на основі раніше отриманого досвіду і раціонального аналізу зовнішніх впливів.
Ми, в нашому курсі, інтелектом будемо називати здатність мозку вирішувати (інтелектуальні) задачі шляхом придбання, запам'ятовування і цілеспрямованого перетворення знань в процесі навчання на досвіді й адаптації до різноманітних обставин.
У цьому визначенні під терміном "знання" мається на увазі не тільки ту інформацію, яка надходить у мозок через органи почуттів. Такого типу знання надзвичайно важливі, але недостатні для інтелектуальної діяльності. Справа в тому, що об'єкти навколишньої середовища мають властивість не тільки впливати на органи почуттів, але і знаходитися один з одним в певних відносинах. Ясно, що для того, щоб здійснювати в навколишньому середовищі інтелектуальну діяльність (або хоча б просто існувати), необхідно мати в системі знань модель цього світу. У цій інформаційній моделі навколишнього середовища реальні об'єкти, їх властивості і відносини між ними не тільки відображаються і запам'ятовуються, а й, як це зазначено в даному визначенні інтелекту, можуть подумки "цілеспрямовано перетворюватися". При цьому істотно те, що формування моделі зовнішнього середовища відбувається "у процесі навчання на досвіді й адаптації до різноманітних обставин".
Ми вжили термін інтелектуальна задача. Для того, щоб пояснити, чим відрізняється інтелектуальна завдання від просто завдання, необхідно ввести термін "алгоритм" - один з наріжних термінів кібернетики.
Під алгоритмом розуміють точне розпорядження про виконання в певному порядку системи операцій для вирішення будь-якої задачі з деякого даного класу (безлічі) завдань. Термін "алгоритм" походить від імені узбецького математика Аль-Хорезмі, який ще в IX столітті запропонував найпростіші арифметичні алгоритми. У математиці та кібернетиці клас задач певного типу вважається вирішеним, коли для її рішення встановлений алгоритм. Знаходження алгоритмів є природною метою людини при вирішенні ним різноманітних класів задач. Відшукування алгоритму для задач деякого даного типу пов'язане з тонкими і складними міркуваннями, які вимагають великої винахідливості і високої кваліфікації. Прийнято вважати, що подібного роду діяльність вимагає участі інтелекту людини. Завдання, пов'язані з віднайденням алгоритму розв'язання класу задач певного типу, будемо називати інтелектуальними.
Що ж стосується завдань, алгоритми вирішення яких вже встановлені, то, як зазначає відомий фахівець у галузі ШІ М. Мінський, "надмірно приписувати їм таке містичне властивості, як" інтелектуальність ". Справді, після того, як такий алгоритм уже знайдений, процес розв'язання відповідних задач стає таким, що його можуть у точності виконати людина, обчислювальна машина (належним чином запрограмована) або робот, що не мають ні найменшого уявлення про сутність самої задачі. Потрібно тільки, щоб особа, що вирішує завдання, була здатна виконувати ті елементарні операції , з яких складається процес, і, крім того, щоб воно педантично і акуратно керувалося запропонованим алгоритмом. Така особа, діючи, як кажуть у таких випадках, чисто машинально, може успішно вирішувати будь-яке завдання аналізованого типу.
Тому видається цілком природним виключити їх класу інтелектуальних такі завдання, для яких існують стандартні методи рішення. Прикладами таких задач можуть служити чисто обчислювальні задачі: рішення системи лінійних алгебраїчних рівнянь, чисельне інтегрування диференціальних рівнянь і т.д. Для вирішення подібного роду завдань є стандартні алгоритми, що представляють собою певну послідовність елементарних операцій, яка може бути легко реалізована у вигляді програми для обчислювальної машини. На противагу цьому для широкого класу інтелектуальних завдань, таких, як розпізнавання образів, гра в шахи, доведення теорем і т.п., навпаки це формальне розбивка процесу пошуку рішення на окремі елементарні кроки часто виявляється дуже складною, навіть якщо сама їх рішення нескладно.
Таким чином, ми можемо перефразувати визначення інтелекту як універсальний сверхалгорітм, який здатний створювати алгоритми вирішення конкретних завдань.
Ще цікавим зауваженням тут є те, що професія програміста, виходячи з наших визначень, є однією з найбільш інтелектуальних, оскільки продуктом діяльності програміста є програми - алгоритми в чистому вигляді. Саме тому, створення навіть елементів ШІ має дуже сильно підвищити продуктивність його праці.
Діяльність мозку (володіє інтелектом), спрямовану на вирішення інтелектуальних завдань, ми будемо називати мисленням, або інтелектуальною діяльністю. Інтелект і мислення органічно пов'язані з вирішенням таких завдань, як доказ теорем, логічний аналіз, розпізнавання ситуацій, планування поведінки, ігри та управління в умовах невизначеності. Характерними рисами інтелекту, що проявляються в процесі вирішення завдань, є здатність до навчання, узагальнення, накопичення досвіду (знань і навичок) і адаптації до умов, що змінюються в процесі вирішення завдань. Завдяки цим якостям інтелекту мозок може вирішувати різноманітні завдання, а також легко перебудовуватися з рішення однієї задачі на іншу. Таким чином, мозок, наділений інтелектом, є універсальним засобом вирішення широкого кола завдань (в тому числі неформалізованих) для яких немає стандартних, заздалегідь відомих методів рішення.
Слід мати на увазі, що існують і інші, чисто поведінкові (функціональні) визначення. Так, за А.Н. Колмогорова, будь-яка матеріальна система, з якою можна досить довго обговорювати проблеми науки, літератури і мистецтва, володіє інтелектом. Іншим прикладом поведінкової трактування інтелекту може слугувати відоме визначення А. Тьюринга. Його сенс полягає в наступному. У різних кімнатах знаходиться люди і машина. Вони не можуть бачити одне одного, але мають можливість обмінюватися інформацією (наприклад, за допомогою електронної пошти). Якщо в процесі діалогу між учасниками гри людям не вдається встановити, що один з учасників - машина, то таку машину можна вважати володіє інтелектом.
До речі цікавий план імітації мислення, запропонований А. Тьюрінгом. "Намагаючись імітувати інтелект дорослої людини, - пише Тьюринг, - ми змушені багато розмірковувати про той процес, в результаті якого людський мозок досяг свого справжнього стану ... Чому б нам замість того, щоб намагатися створити програму, яка імітує інтелект дорослої людини, не спробувати створити програму , яка імітувала б інтелект дитини? Адже якщо інтелект дитини отримує відповідне виховання, він стає інтелектом дорослої людини ... Наш розрахунок полягає в тому, що пристрій, йому подібне, може бути легко запрограмоване ... Таким чином, ми розчленуємо нашу проблему на дві частини: на завдання побудови "програми-дитини" і завдання "виховання" цієї програми ".
Забігаючи наперед, можна сказати, що саме цей шлях використовують практично всі системи ШІ. Адже зрозуміло, що практично неможливо закласти всі знання в досить складну систему. Крім того, тільки на цьому шляху виявляться перераховані вище ознаки інтелектуальної діяльності (накопичення досвіду, адаптація тощо).
2. Історія розвитку систем ІІ
Історично склалися три основні напрями в моделюванні ШІ.У рамках першого підходу об'єктом досліджень є структура і механізми роботи мозку людини, а кінцева мета полягає в розкритті таємниць мислення. Необхідними етапами досліджень у цьому напрямку є побудова моделей на основі психофізіологічних даних, проведення експериментів з ними, висування нових гіпотез щодо механізмів інтелектуальної діяльності, удосконалення моделей і т.д.
Другий підхід в якості об'єкта дослідження розглядає ШІ. Тут мова йде про моделювання інтелектуальної діяльності за допомогою обчислювальних машин. Метою робіт у цьому напрямку є створення алгоритмічного і програмного забезпечення обчислювальних машин, що дозволяє вирішувати інтелектуальні задачі не гірше людини.
Нарешті, третій підхід орієнтований на створення змішаних людино-машинних, або, як ще кажуть, інтерактивних інтелектуальних систем, на симбіоз можливостей природного і штучного інтелекту. Найважливішими проблемами в цих дослідженнях є оптимальний розподіл функцій між природним і штучним інтелектом і організація діалогу між людиною і машиною.
Найпершими інтелектуальними завданнями, які стали вирішуватися за допомогою ЕОМ були логічні ігри (шашки, шахи), доказ теорем. Хоча, правда тут треба відзначити ще кібернетичні іграшки типу "електронної миші" Клода Шеннона, що керувалася складної релейного схемою. Ця мишка могла "дослідити" лабіринт, і знаходити вихід з нього. А крім того, вміщена у вже відомий їй лабіринт, вона не шукала вихід, а відразу ж, не заглядаючи в тупикові ходи, виходила з лабіринту.
Американський кібернетик А. Самуель склав для обчислювальної машини програму, яка дозволяє їй грати в шашки, причому в ході гри машина навчається або, принаймні, створює враження, що навчається, покращуючи свою гру на основі накопиченого досвіду. У 1962 р. ця програма зіграли з Р. Нілі, найсильнішим шашкістом в США і перемогла.
Яким чином машині вдалося досягти такого високого класу гри?
Природно, що в машину були програмно закладені правила гри так, що вибір чергового ходу був підпорядкований цими правилами. На кожній стадії гри машина вибирала черговий хід з безлічі можливих ходів відповідно до певного критерію якості гри. У шашках (як і в шахах) зазвичай невигідно втрачати свої фігури, і, навпаки, вигідно брати фігури супротивника. Гравець (будь він людина чи машина), який зберігає рухливість своїх фігур і право вибору ходів і в той же час тримає під боєм велике число полів на дошці, зазвичай грає краще за свого супротивника, не додає значення цих елементів гри. Описані критерії хорошої гри зберігають свою силу протягом всієї гри, але є й інші критерії, які відносяться до окремих її стадіях - дебюту, міттендшпілю, ендшпілю.
Розумно поєднуючи такі критерії (наприклад, у вигляді лінійної комбінації з експериментально бираються коефіцієнтами або більш складним чином), можна для оцінки чергового ходу машини отримати деякий числовий показник ефективності - оціночну функцію. Тоді машина, порівнявши між собою показники ефективності чергових ходів, вибере хід, відповідний найбільшому показнику. Подібна автоматизація вибору чергового ходу не обов'язково забезпечує оптимальний вибір, але все ж це якийсь вибір, і на його основі машина може продовжувати гру, удосконалюючи свою стратегію (образ дії) в процесі навчання на минулому досвіді. Формально навчання полягає в підстроюванні параметрів (коефіцієнтів) оцінної функції на основі аналізу проведених ходів та ігор з урахуванням їх результату.
На думку А. Самуеля, машина, яка використовує цей вид навчання, може навчитися грати краще, ніж середній гравець, за відносно короткий період часу.
Можна сказати, що всі ці елементи інтелекту, продемонстровані машиною в процесі гри в шашки, повідомлені їй автором програми. Частково це так. Але не слід забувати, що програма ця не є "жорсткою", заздалегідь продуманої у всіх деталях. Вона удосконалює свою стратегію гри в процесі самонавчання. І хоча процес "мислення" у машини істотно різниться від того, що відбувається в мозку грає в шашки людини, вона здатна у нього виграти.
Яскравим прикладом складної інтелектуальної гри до недавнього часу були шахи. У 1974 р. відбувся міжнародний шаховий турнір машин, забезпечених відповідними програмами. Як відомо, перемогу на цьому турнірі здобула радянська машина з шаховою програмою "Каїсса".
Чому тут вжито "до недавнього часу"? Справа в тому, що недавні події показали, що незважаючи на досить велику складність шахів, і неможливість, у зв'язку з цим зробити повний перебір ходів, можливість перебору їх на велику глибину, ніж зазвичай, дуже збільшує шанси на перемогу. Наприклад, за повідомленнями у пресі, комп'ютер фірми IBM, який переміг Каспарова, мав 256 процесорів, кожний з яких мав 4 Гб дискової пам'яті і 128 Мб оперативної. Весь цей комплекс міг прораховувати більш 100'000'000 ходів у секунду. До недавнього часу рідкістю був комп'ютер, який може робити таку кількість цілочисельних операцій в секунду, а тут ми говоримо про ходах, які повинні бути генеровані і для яких прораховані оціночні функції. Хоча з іншого боку, цей приклад свідчить про могутність і універсальності переборних алгоритмів.
В даний час існують і успішно застосовуються програми, що дозволяють машинам грати у ділові або військові ігри, що мають велике прикладне значення. Тут також надзвичайно важливо надати програмами властиві людині здатність до навчання та адаптації. Однією з найбільш цікавих інтелектуальних завдань, також має величезне прикладне значення, є задача навчання розпізнавання образів і ситуацій. Рішенням її займалися і продовжують займатися представники різних наук - фізіологи, психологи, математики, інженери. Такий інтерес до задачі стимулювався фантастичними перспективами широкого практичного використання результатів теоретичних досліджень: читають автомати, системи штучного інтелекту, що ставлять медичні діагнози, які проводять криміналістичну експертизу і т.п., а також роботи, здатні розпізнавати й аналізувати складні сенсорні ситуації.
У 1957 р. американський фізіолог Ф. Розенблатт запропонував модель зорового сприйняття і розпізнавання - перцептрон. Поява машини, здатної навчатися поняттям і розпізнавати запропоновані об'єкти, виявилося надзвичайно цікавим не тільки фізіологам, але і представникам інших областей знання і породило великий потік теоретичних і експериментальних досліджень.
Перцептрон або будь-яка програма, що імітує процес розпізнавання, працюють в двох режимах: в режимі навчання і в режимі розпізнавання. У режимі навчання хтось (людина, машина, робот або природа), що грає роль учителя, пред'являє машині об'єкти та про кожного з них повідомляє, до якого поняття (класу) він належить. За цими даними будується вирішальне правило, що є, по суті, формальним описом понять. У режимі розпізнавання машині пред'являються нові об'єкти (взагалі кажучи, відмінні від раніше пред'явлених), і вона повинна їх класифікувати, по можливості, правильно.
Що ж стосується моделювання логічного мислення, то гарною модельної завданням тут може служити задача автоматизації доведення теорем. Починаючи з 1960 р., був розроблений ряд програм, здатних знаходити докази теорем в численні предикатів першого порядку. Ці програми мають, за словами американського спеціаліста в галузі ШІ Дж. Маккатті, "здоровим глуздом", тобто здатністю робити дедуктивні висновки.
У програмі К. Гріна та ін, що реалізує питально-відповідну систему, знання записуються на мові логіки предикатів у вигляді набору аксіом, а питання, що задаються машині, формулюються як підлягають доведенню теореми. Великий інтерес представляє "інтелектуальна" програма американського математика Хао Ванга. Ця програма за 3 хвилини роботи IBM-704 вивела 220 відносно простих лем і теорем з фундаментальної математичної монографії, а потім за 8.5 хв видала докази ще 130 більше складних теорем, частина з яких ще не була виведена математиками. Правда, до цих пір жодна програма не вивела і не довела жодної теореми, яка б, що називається "конче" була б потрібна математикам і була б принципово нової.
Дуже великим напрямком систем ШІ є роботехніка. У чому основна відмінність інтелекту робота від інтелекту універсальних обчислювальних машин?
Для відповіді на це питання доречно згадати належить великому російському фізіологові І.М. Сеченову вислів: "... все нескінченна різноманітність зовнішніх проявів мозкової діяльності зводиться остаточно лише до одного явища - м'язовому руху". Іншими словами, вся інтелектуальна діяльність людини спрямована в кінцевому рахунку на активну взаємодію із зовнішнім світом за допомогою рухів. Точно так само елементи інтелекту робота служать перш за все для організації його цілеспрямованих рухів. У той же час основне призначення чисто комп'ютерних систем ШІ полягає у вирішенні інтелектуальних завдань, що носять абстрактний або допоміжний характер, які зазвичай не пов'язані ні зі сприйняттям навколишнього середовища за допомогою штучних органів почуттів, ні з організацією рухів виконавчих механізмів.
Перших роботів важко назвати інтелектуальними. Тільки в 60-х роках з'явилися очувствленние роботи, які управлялися універсальними комп'ютерами. Наприклад в 1969 р. в Електротехнічній лабораторії (Японія) почалася розробка проекту "промисловий інтелектуальний робот". Мета цієї розробки - створення очуствленного маніпуляційного робота з елементами штучного інтелекту для виконання складально-монтажних робіт з візуальним контролем.
Маніпулятор робота має шість ступенів свободи і управляється міні-ЕОМ NEAC-3100 (об'єм оперативної пам'яті 32000 слів, обсяг зовнішньої пам'яті на магнітних дисках 273000 слів), формує необхідну програмний рух, що відпрацьовується стежить електрогідравлічної системою. Схват маніпулятора оснащений тактильними датчиками.
В якості системи зорового сприйняття використовуються дві телевізійні камери, забезпечені червоно-зелено-синіми фільтрами для розпізнавання кольору предметів. Поле зору телевізійної камери розбите на 64 * 64 осередків. У результаті обробки отриманої інформації грубо визначається область, займана цікавлять робота предметом. Далі, з метою детального вивчення цього предмета виявлена область знову ділиться на 4096 осередків. У тому випадку, коли предмет не поміщається в обраний "віконце", воно автоматично переміщається, подібно до того, як людина ковзає поглядом по предмету. Робот Електротехнічній лабораторії був здатний розпізнавати прості предмети, обмежені площинами й циліндричними поверхнями при спеціальному освітленні. Вартість даного експериментального зразка становила приблизно 400000 доларів.
Поступово характеристики роботів монотонно поліпшувалися, Але до цих пір вони ще далекі по тями від людини, хоча деякі операції вже виконують на рівні кращих жонглерів. Приміром утримують на лезі ножа кульку від настільного тенісу.
Ще мабуть тут можна виділити роботи київського Інституту кібернетики, де під керівництвом Н.М. Амосова і В.М. Глушкова (нині покійного) ведеться комплекс досліджень, спрямованих на розробку елементів інтелекту роботів. Особлива увага в цих дослідженнях приділяється проблемам розпізнавання зображень і мови, логічного висновку (автоматичного доведення теорем) та управління за допомогою нейроподібних мереж.
До прикладу можна розглянути створений ще в 70-х роках макет транспортного автономного інтегрального робота (ТАЇР). Конструктивно ТАІР представляє собою триколісний шасі, на якому змонтована сенсорна система і блок управління. Сенсорна система включає в себе наступні засоби очуствленія: оптичний далекомір, навігаційна система з двома радіомаяками і компасом, контактні датчики, датчики кутів нахилу візки, таймер і ін І особливість, яка відрізняє ТАІР від багатьох інших систем, створених у нас і за кордоном, це те, що в його складі немає комп'ютера в тому вигляді, до якого ми звикли. Основу системи управління складає бортова нейроподібна мережу, на якій реалізуються різні алгоритми обробки сенсорної інформації, планування поведінки та управління рухом робота.
У кінці цього дуже короткого огляду розглянемо приклади великомасштабних експертних систем.
MICIN - експертна система для медичної діагностики. Розроблена групою з інфекційних захворювань Стенфордського університету. Ставить відповідний діагноз, виходячи з представлених їй симптомів, і рекомендує курс медикаментозного лікування будь-якої з діагностованих інфекцій. База даних складається з 450 правил.
PUFF - аналіз порушення дихання. Дана система являє собою MICIN, з якої видалили дані по інфекцій і вставили дані про легеневі захворювання.
DENDRAL - розпізнавання хімічних структур. Дана система найстаріша, з мають звання експертних. Перші версії даної системи з'явилися ще в 1965 році під все тому ж Стенфордському університеті. Користувач дає системі DENDRAL деяку інформацію про речовину, а також дані спектрометрії (інфрачервоної, ядерного магнітного резонансу і мас-спектрометрії), і та у свою чергу видає діагноз у вигляді відповідної хімічної структури.
PROSPECTOR - експертна система, створена для сприяння пошуку комерційно виправданих родовищ корисних копалин.
Архітектура та основні складові частини систем ШІ.
Різні підходи до побудови систем ШІ (логічний, структурний, еволюційний, імітаційний) і методи представлення знань. Короткий ознайомлення з даними підходами. Допоміжні системи (розпізнавання образів зорових і звукових, ідентифікація, моделювання, жорстке програмування) та їх місце в системах ШІ.
Різні підходи до побудови систем ШІ
Існують різні підходи до побудови систем ШІ. Це поділ не є історичним, коли одна думка поступово поміняє інше, і різні підходи існують і зараз. Крім того, оскільки по-справжньому повних систем ШІ в даний час немає, то не можна сказати, що якийсь підхід є правильним, а якийсь помилковим.Для початку коротко розглянемо логічний підхід. Чому він виник? Адже людина займається аж ніяк не тільки логічними вигадками. Це висловлювання звичайно вірно, але саме здатність до логічного мислення дуже сильно відрізняє людину від тварин.
Основою для даного логічного підходу служить Булева алгебра. Кожен програміст знайомий з нею і з логічними операторами з тих пір, коли він освоював оператор IF. Свій подальший розвиток Булева алгебра одержала у вигляді обчислення предикатів - у якому вона розширена за рахунок введення предметних символів, відносин між ними, кванторів існування та загальності. Практично кожна система ШІ, побудована на логічному принципі, є машиною доказу теорем. При цьому вихідні дані зберігаються в базі даних у вигляді аксіом, правила логічного висновку як відносини між ними. Крім того, кожна така машина має блок генерації цілі, і система виводу намагається довести дану мету як теорему. Якщо мета доведена, то трасування застосованих правил дозволяє отримати ланцюжок дій, необхідних для реалізації поставленої мети. Потужність такої системи визначається можливостями генератора цілей і машиною доказу теорем.
Звичайно можна сказати, що виразності алгебри висловлювань не вистачить для повноцінної реалізації ІІ, але варто згадати, що основою всіх існуючих ЕОМ є біт - комірка пам'яті, яка може приймати значення тільки 0 і 1. Таким чином було б логічно припустити, що все, що можливо реалізувати на ЕОМ, можна було б реалізувати і у вигляді логіки предикатів. Хоча тут нічого не говориться про те, за який час.
Домогтися більшої виразності логічного підходу дозволяє таке порівняно новий напрям, як нечітка логіка. Основним її відмінністю є те, що правдивість висловлювання може брати в ній крім так / ні (1 / 0) ще й проміжні значення - не знаю (0.5), пацієнт швидше живий, ніж мертвий (0.75), пацієнт швидше мертвий, ніж живий ( 0.25). Даний підхід більше схожий на мислення людини, оскільки він на питання рідко відповідає тільки так чи ні. Хоча правда на іспиті будуть прийматися тільки відповіді з розряду класичної булевої алгебри.
Для більшості логічних методів характерна велика трудомісткість, оскільки під час пошуку докази можливий повний перебір варіантів. Тому даний підхід вимагає ефективної реалізації обчислювального процесу, і хороша робота зазвичай гарантується при порівняно невеликому розмірі бази даних.
Під структурним підходом ми маємо на увазі тут спроби побудови ШІ шляхом моделювання структури людського мозку. Однією з перших таких спроб був перцептрон Френка Розенблатта. Основний модельованої структурною одиницею в перцептронах (як і в більшості інших варіантів моделювання мозку) є нейрон.
Пізніше виникли і інші моделі, які в народі зазвичай відомі під терміном "нейронні мережі" (НС). Ці моделі розрізняються за будовою окремих нейронів, за топологією зв'язків між ними і за алгоритмами навчання. Серед найбільш відомих зараз варіантів НС можна назвати НС зі зворотним поширенням помилки, мережі Хопфілда, стохастичні нейронні мережі.
НС найбільш успішно застосовуються в задачах розпізнавання образів, в тому числі сильно зашумлених, проте є і приклади успішного застосування їх для побудови власне систем ШІ, це вже раніше згадуваний ТАІР.
Для моделей, побудованих за мотивами людського мозку характерна не занадто більша виразність, легке розпаралелювання алгоритмів, і пов'язана з цим висока продуктивність паралельно реалізованих НС. Також для таких мереж характерно одне властивість, яка дуже зближує їх з людським мозком - нейронні мережі працюють навіть за умови неповної інформації про навколишнє середовище, тобто як і людина, вони на питання можуть відповідати не тільки "так" і "ні" а й "не знаю точно, але скоріше так".
Досить велике поширення одержав й еволюційний підхід. При побудові систем ШІ з даного підходу основну увагу приділяється побудові початкової моделі, і правилам, за якими вона може змінюватися (еволюціонувати). Причому модель може бути складена з найрізноманітніших методів, це може бути і НС і набір логічних правил і будь-яка інша модель. Після цього ми вмикаємо комп'ютер і він, на підставі перевірки моделей відбирає найкращі з них, на підставі яких по всіляких правилами генеруються нові моделі, з яких знову вибираються найкращі і т.д.
У принципі можна сказати, що еволюційних моделей як таких не існує, існує тільки еволюційні алгоритми навчання, але моделі, отримані при еволюційному підході мають деякі характерні особливості, що дозволяє виділити їх в окремий клас.
Такими особливостями є перенесення основної роботи розробника з побудови моделі на алгоритм її модифікації і те, що отримані моделі практично не супроводжують витяганню нових знань про середовище, що оточує систему ШІ, тобто вона стає як би річчю в собі.
Ще один широко використовуваний підхід до побудови систем ШІ - імітаційний. Даний підхід є класичним для кібернетики з одним із її базових понять - "чорним ящиком" (чя). Чя - пристрій, програмний модуль або набір даних, інформація про внутрішню структуру та зміст яких відсутні повністю, але відомі специфікації вхідних і вихідних даних. Об'єкт, поведінка якого імітується, якраз і являє собою такий "чорний ящик". Нам не важливо, що у нього і у моделі всередині і як він функціонує, головне, щоб наша модель в аналогічних ситуаціях вела себе так само.
Таким чином тут моделюється інша властивість людини - здатність копіювати те, що роблять інші, не вдаючись у подробиці, навіщо це потрібно. Найчастіше ця здатність економить йому масу часу, особливо на початку його життя.
Основним недоліком імітаційного підходу також є низька інформаційна здатність більшості моделей, побудованих з його допомогою.
З чя пов'язана одна дуже цікава ідея. Хто б хотів жити вічно? Я думаю, що майже всі скажуть на це питання "я".
Уявімо собі, що за нами спостерігає якийсь пристрій, який стежить за тим, що в якихось ситуаціях ми робимо, говоримо. Спостереження йде за величинами, які надходять до нас на вхід (зір, слух, смак, тактильні, вестибулярні і т.д.) і за величинами, які виходять від нас (мова, рух тощо). Таким чином людина виступає тут як типовий чя.
Далі цей пристрій намагається відбудувати якусь модель таким чином, щоб за певних сигнали на вході людини, вона видавала на виході ті ж дані, що й людина. Якщо дана витівка буде коли-небудь реалізована, то для всіх сторонніх спостерігачів така модель буде тією ж особою, що і реальна людина. А після його смерті вона, буде висловлювати ті думки, які, ймовірно, висловлював би й змодельований чоловік.
Ми можемо піти далі і скопіювати цю модель і отримати брата близнюка з точно такими ж "думками".
Можна сказати, що "це звичайно все цікаво, але при чому тут я? Адже ця модель тільки для інших буде мною, але всередині її буде порожнеча. Копіюються тільки зовнішні атрибути, але я після смерті вже не буду думати, моя свідомість погасне ( для віруючих людей слово "згасне" необхідно замінити на "покине цей світ") ". Що ж це так. Але спробуємо піти далі.
Згідно філософським уявленням автора даного курсу, свідомість являє собою порівняно невелику надбудову над нашою підсвідомістю, яка стежить за активністю деяких центрів головного мозку, таких як центр мовлення, кінцевої обробки зорових образів, після чого "повертає" ці образи на початкові ступені обробки даної інформації. При цьому відбувається повторна обробка цих образів, ми ніби бачимо і чуємо, що думає наш мозок. При цьому з'являється можливість уявного моделювання навколишньої дійсності при нашому "активному" участі в даному процесі. І саме наш процес спостереження за діяльністю цих небагатьох центрів є тим, що ми називаємо свідомістю. Якщо ми "бачимо" і "чуємо" наші думки, ми в свідомості, якщо ні, то ми знаходимося в несвідомому стані.
Якщо б ми змогли змоделювати роботу саме цих небагатьох "свідомих" нервових центрів (робота яких правда заснована на діяльності всього іншого мозку) у якості одного чя, і роботу "супервізора" в якості іншого чя, то можна було б з упевненістю говорити, що " так, дана модель думає, причому так само, як і я ". Тут я нічого не хочу говорити про те, як отримати дані про роботу цих нервових центрів, оскільки на мій погляд сьогодні немає нічого такого, що дозволило б стежити за мозком людини роками і при цьому не завадило б його роботі і житті.
І закінчуючи побіжне ознайомлення з різними методами і підходами до побудови систем ШІ, хотілося б відзначити, що на практиці дуже чіткої межі між ними немає. Дуже часто зустрічаються змішані системи, де частина роботи виконується за одним типом, а частина по іншому.
головний клас віконного інтерфейсу - TCheckersWindow
головний думаючий, що грає клас - BOARD
КОРОТКИЙ ОПИС АЛГОРИТМУ
УПРАВЛІННЯ проводиться через віконний інтерфейсний клас TCheckersWindow.
Хід людини починається натисканням лівої кнопки мишки над фішкою (при цьому запускається
функція WMLButtonDown () з класу TCheckersWindow), далі не відпускаючи кнопку курсор
пересувається на нову позицію фішки і кнопка відпускається (при цьому запускається
функція WMLButtonUp () з класу TCheckersWindow). Розглянемо роботу цих двох
функцій докладніше (див. примітки в тексті функції):
Функція WMLButtonDown ():
void TCheckersWindow:: WMLButtonDown (TMessage &) / / ===== ПОЧИНАЄМО ХІД ======
{
POINT Point;
if (WhoseTurn == Black) / / ===== перевіряє, чи дійсно ХОДИТЬ ЛЮДИНА =====
return;
SetCapture (HWindow);
GetCursorPos (& Point);
ScreenToClient (HWindow, & Point);
MoveStartPoint = bd-> GetValidSquare (Point, WhoseTurn);
if (MoveStartPoint. x)
{
MovingPieceType = bd-> GetPieceType (MoveStartPoint);
HDC hDC = GetDC (HWindow);
bd-> ClearSquare (hDC, MoveStartPoint);
HoldingPiece = TRUE;
ReleaseDC (HWindow, hDC);
}
}
Функція WMLButtonUp ():
void TCheckersWindow:: WMLButtonUp (TMessage &)
{
POINT Point;
ReleaseCapture ();
if (! HoldingPiece | | WhoseTurn == Black)
return;
GetCursorPos (& Point);
ScreenToClient (HWindow, & Point);
MoveEndPoint = bd-> GetEmptySquare (Point);
HDC hDC = GetDC (HWindow);
if (MoveEndPoint. x & & bd-> UserMove (MoveStartPoint, MoveEndPoint))
{/ / ==== ЯКЩО ЛЮДИНА МОЖЕ СЮДИ ПОСТАВИТИ ФІШКИ ... =====
bd-> RedrawBoard (hDC); / / ========= ТО Перемальовує ДОШКУ =======
EnableMenuItem (hMenu, CM_UNDO, MF_BYCOMMAND | MF_ENABLED);
EnableMenuItem (hMenu, CM_REDO, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
if (! bd-> AnotherJump ()) / / ===== МОЖНА ЗРОБИТИ ПОВТОРНИЙ ХІД? ========
{
if (bd-> NoMoreBlack ()) / / ==== ЯКЩО БІЛЬШЕ НЕОСТАЛОСЬ фішок КОМП'ЮТЕРА ... . ===
{
if (GetApplication () -> ExecDialog (new TEndDialog (this, "UserWonDlg")) / / ТО ЛЮДИНА ВИГРАВ!
== IDYES)
{
PostMessage (HWindow, WM_COMMAND, CM_FILENEW, 0L);
ReleaseDC (HWindow, hDC);
return;
}
else
{
PostMessage (HWindow, WM_COMMAND, CM_EXIT, 0L);
ReleaseDC (HWindow, hDC);
return;
}
}
PostMessage (HWindow, WM_COMMAND, CM_MOVE, 0L); / / == Перемикати НА ХІД ===
} / / ======= КОМП'ЮТЕРА =======
else / / НЕЯВНИХ ВИКЛИК ФУНКЦІЇ
; / / ComputersMove ()
}
else
{
bd-> DrawPiece (hDC, MovingPieceType, MoveStartPoint);
}
HoldingPiece = FALSE;
ReleaseDC (HWindow, hDC);
}
Функція ComputersMove ():
void TCheckersWindow:: ComputersMove (RTMessage)
{
bd-> EndUsersTime ();
WhoseTurn = Black;
EnableMenuItem (hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem (hMenu, 1, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem (hMenu, 3, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
ModifyMenu (hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_STOP, "& Stop");
DrawMenuBar (HWindow);
bd-> ComputersTurn (); / / ======= перемикається на роботу ІІ ========
HDC hDC = GetDC (HWindow);
bd-> RedrawBoard (hDC);
ReleaseDC (HWindow, hDC);
WhoseTurn = Red;
POINT CursorPoint;
GetCursorPos (& CursorPoint);
ScreenToClient (HWindow, & CursorPoint);
# Pragma warn - stv
if (PtInRect (& MainWndRect, CursorPoint))
/ * SetCursor (CursorHand) * /;
# Pragma warn + stv
ModifyMenu (hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_MOVE, "move you");
EnableMenuItem (hMenu, 0, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem (hMenu, 1, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem (hMenu, 3, MF_BYPOSITION | MF_ENABLED);
DrawMenuBar (HWindow);
if (bd-> NoMoreRed ()) / / ==== ЯКЩО БІЛЬШЕ НЕОСТАЛОСЬ фішок ЛЮДИНИ ... . ===
{
if (GetApplication () -> ExecDialog (new TEndDialog (this, "GameWonDlg")) / / === ТО КОМП'ЮТЕР ===
== IDYES) / / ====== ВИГРАВ ======
{
PostMessage (HWindow, WM_COMMAND, CM_FILENEW, 0L);
return;
}
else
{
PostMessage (HWindow, WM_COMMAND, CM_EXIT, 0L);
return;
}
}
bd-> StartUsersTime (); / / ====== ХІД ЛЮДИНИ ========
}
BOOL BOARD:: ComputersTurn ()
{
int iter, i, val, row = 0, col = 0;
double t;
time_t itime1, itime2;
long lNodes;
int alpha = - MAXINT, beta = MAXINT;
StopSearch = FALSE;
ClearRedoStack ();
memcpy (SavedBoard, Board, sizeof (Board));
if (! OnlyOneMove (Black, & row, col &))
{
Nodes = 0;
time (& start_t);
PreEvaluate (); / / ======= ПОЛІТИКА ІГРИ (нападають або відбивають) =====
/ * Clear out the best-variation table * /
for (i = 0; i <= MAXPLY; + + i)
{
BestVar [i] [i]. org. SetRow (0);
BestVar [0] [i]. org. SetRow (0);
}
/ * Clear out the Killer table * /
for (i = 0; i <= MAXPLY; + + i)
{
Killer [i] [0]. org. SetRow (0);
Killer [i] [0]. Value = - 1;
}
for (iter = IterFlag? 1: SearchDepth; iter <= SearchDepth; + + iter)
{
lNodes = Nodes;
time (& itime1);
val = Evaluate (alpha, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
if (val> = beta)
{
val = Evaluate (alpha, MAXINT, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
else
{
if (val <= alpha)
{
val = Evaluate (- MAXINT, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
}
alpha = val - 12;
beta = val + 12;
/ * Seed the killer table with the best variation * /
for (i = 0; BestVar [0] [i]. org. GetRow (); + + i)
{
memcpy (& Killer [i] [0], & BestVar [0] [i], sizeof (MOVE));
Killer [i] [0]. Value = 1;
/ * Eliminate the other killer move * /
Killer [i] [1]. Value = - 1;
Killer [i] [1]. org. SetRow (0);
}
/ * Clear the rest of the killer table * /
do
{
Killer [i] [0]. org. SetRow (0);
Killer [i] [1]. org. SetRow (0);
}
while (i + + <MAXPLY);
time (& itime2);
t = difftime (itime2, itime1);
DisplaySearchStats (iter, val, Nodes - lNodes, t);
}
time (& end_t);
if ((t = difftime (end_t, start_t))! = 0)
{
sprintf (buf, "% .0 f", t);
sprintf (buf, "% ld", Nodes);
ComputerTotalTime + = t;
}
else
{
sprintf (buf, "% ld", Nodes);
}
for (i = 0; Man [Board [BestVar [0] [i]. org. GetRow ()]
[BestVar [0] [i]. org. GetCol ()]. What]. GetSide () == Black; + + i)
{
MakeActualMove (BestVar [0] [i]);
}
}
TimeToStr (buf, ComputerTotalTime);
return (TRUE);
}
Функція PreEvaluate () розробляє політику гри:
void BOARD:: PreEvaluate ()
{
int i, j, xman, inside;
int tBSizeDiv2 = BoardSize>> 1; / / (BoardSize / 2)
/************************************************* ********
This code gets a rough idea as to who is ahead in Material.
************************************************** ********/
Material [Red] = 0;
Material [Black] = 0;
Man [REDMAN]. SetValue (100);
Man [BLACKMAN]. SetValue (100);
Man [REDKING]. SetValue (140);
Man [BLACKKING]. SetValue (140);
Man [EMPTY]. SetValue (0);
Man [OFFBOARD]. SetValue (0);
for (i = 1; i <= BoardSize; + + i)
{
for (j = 1; j <= BoardSize; + + j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide ()] + = Man [xman]. GetValue ();
}
}
/************************************************* ***
Now adjust the Material weights based on who is ahead.
This is to encourage the fellow who is winning to exchange pieces
and the fellow who is behind to not exchange pieces.
If Material is dead even then you shouldn't try to force exchanges
just on general principles.
************************************************** *** /
if (Material [Red]> = Material [Black])
{
--Man [REDMAN];
- Man [REDKING];
}
else
{
--Man [BLACKMAN];
- Man [BLACKKING];
}
/************************************************* ***
Examine each and every square and calculate the bonus values.
************************************************** *** /
for (i = 1; i <= BoardSize; + + i)
{
for (j = 1; j <= BoardSize; + + j)
{
inside = (j> 1 & & j <BoardSize)? 1: 0;
SValue [i] [j] [REDMAN] = Man [REDMAN]. GetValue () + inside;
SValue [i] [j] [REDKING] = Man [REDKING]. GetValue () + inside;
SValue [i] [j] [BLACKMAN] = Man [BLACKMAN]. GetValue () + inside;
SValue [i] [j] [BLACKKING] = Man [BLACKKING]. GetValue () + inside;
/ * Bonus points for central squares * /
if (abs (tBSizeDiv2 - i) <2 & & abs (tBSizeDiv2 - j) <3)
{
+ + SValue [i] [j] [REDMAN];
+ + SValue [i] [j] [REDKING];
+ + SValue [i] [j] [BLACKMAN];
+ + SValue [i] [j] [BLACKKING];
}
/ * Bonus for non-Crown piece advancement * /
if (i> 2)
{
SValue [i] [j] [REDMAN] + = i - 2;
}
if (i <BoardSize - 2)
{
SValue [i] [j] [BLACKMAN] + = BoardSize - i - 1;
}
if (i == 1)
+ + SValue [i] [j] [REDMAN];
if (i == BoardSize)
+ + SValue [i] [j] [BLACKMAN];
}
}
Material [Red] = 0;
Material [Black] = 0;
for (i = 1; i <= BoardSize; + + i)
{
for (j = 1; j <= BoardSize; + + j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide ()] + = SValue [i] [j] [xman];
}
}
}
Функція Evaluate () представляє безпосередньо функцію ШІ. Основний принцип -
на глибину depth анадблжлізіруются можливі ходи комп'ютера і ходи у людини - шукаємо найкращу стратегію:
int BOARD:: Evaluate (int alpha, int beta, SIDE player, int row, int col, int limit, int ply)
{
MOVE * list = new MOVE [MAXMOVES];
MOVE * mptr, * endptr;
int NumMoves, val;
int num_back = 0;
int retval = 0;
int t1 = WIN - 2 - ply;
int plyp1 = ply + 1;
if (StopSearch)
goto END_EVALUATE;
+ + Nodes;
if ((NumMoves = Lmg (list, player, row, col, ply)) == 0)
{
retval = LOSS + ply;
goto END_EVALUATE;
}
MessageScan ();
if (StopSearch)
{
retval = 0;
goto END_EVALUATE;
}
if (list-> Quiescent (limit, NumMoves, ply))
{
retval = (Material [player] - Material [OPLAYER] + (NumMoves> 3? 1: 0));
goto END_EVALUATE;
}
for (mptr = list, endptr = mptr + NumMoves; mptr <endptr & & alpha <t1; mptr + +)
{
MakeMove (* mptr);
if (mptr-> Capture! = EMPTY)
{
if (! (mptr-> Crown) & & CanJump (player, mptr-> dest. GetRow (), mptr-> dest. GetCol ()))
{
val = Evaluate (alpha, beta, player, mptr-> dest. GetRow (), mptr-> dest. GetCol (), limit, plyp1);
}
else
{
val = Evaluate (- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
}
else
{
if (limit == 0 | | NumMoves == 1)
{
val = Evaluate (- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
else
{
val = Evaluate (- beta, - alpha, OPLAYER, 0, 0, limit? limit - 1: 0, plyp1) * - 1;
}
}
UnMakeMove (* mptr);
if (val> alpha)
{
if (val> = beta)
{
if (KillerFlag)
UpdateKillerTable (* mptr, ply);
retval = beta;
goto END_EVALUATE;
}
else
{
alpha = val;
+ + Num_back;
UpdateBestVariation (mptr, ply);
}
}
BestVar [plyp1] [plyp1]. org. SetRow (0);
}
retval = alpha;
END_EVALUATE:
delete list;
return retval;
}
Допоміжна функція GenMoves () генерурует можливі ходи і
записує їх у список:
/********************************************
generates the list of moves for a given player at a row, col
returns the number of legal moves found
********************************************/
int BOARD:: GenMoves (MOVE * list, int row, int col)
{
int NumMoves;
int what;
int trow1 = row + 1, tcol1 = col + 1, trowm1 = row - 1, tcolm1 = col - 1;
NumMoves = 0;
what = Board [row] [col]. What;
if (what == REDKING | | what == BLACKKING | | what == BLACKMAN)
{
if (Board [trowm1] [tcolm1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trowm1);
list-> dest. SetCol (tcolm1);
list-> Capture = EMPTY;
list-> Crown = ((row == 2) & & (what == BLACKMAN));
+ + NumMoves;
+ + List;
}
if (Board [trowm1] [tcol1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trowm1);
list-> dest. SetCol (tcol1);
list-> Capture = EMPTY;
list-> Crown = ((row == 2) & & (what == BLACKMAN));
+ + NumMoves;
+ + List;
}
}
if (what == REDKING | | what == BLACKKING | | what == REDMAN)
{
if (Board [trow1] [tcolm1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trow1);
list-> dest. SetCol (tcolm1);
list-> Capture = EMPTY;
list-> Crown = ((row == BoardSize - 1) & & (what == REDMAN));
+ + NumMoves;
+ + List;
}
if (Board [trow1] [tcol1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trow1);
list-> dest. SetCol (tcol1);
list-> Capture = EMPTY;
list-> Crown = ((row == BoardSize - 1) & & (what == REDMAN));
+ + NumMoves;
+ + List;
}
}
return (NumMoves);
}
BC30RTL. DLL
OWL31. DLL
TCLASS31. DLL
У текстовому файлі DEPTH зберігається єдина настройка гри - глибина аналізу ходів, за умовчанням вона встановлена в 3 - середній рівень гри в шашки.
Меню гри напрочуд проста і складається з єдиного пункту - "move you" - пропуск ходу.
Нижче наведено два екранні копії програми.
Початок гри
Була розроблена відносно нескладна функція ШІ, головними завданнями якої є передбачення на встановлену глибину своїх ходів і ходів противника. Це пророцтво базується на виборі найкращих ходів з обох сторін. На фінальному етапі функція ШІ обирає найбільш вигідну для комп'ютера ланцюжок ходів.
Програма відрізняється від існуючих на ринку простотою інтерфейсу і налаштувань.
2. Касаткін А.І., Вальвачев О.М. Професійне програмування на мові Сі. Мн., 1992. 240 С.
3. Нейбауер О. Моя перша програма на С / С + +. П., 1995. 368 С.
4. Бруно Бабе. Просто і ясно про Borland C + +. М., 1996. 400 С.
5. Шамас Н.К. Основи С + + і об'єктно-орієнтованого програмування. К., 1996. 448 С.
6. Довідник по класах Borland C + + 4.0.К., 1994.256 С.
7. ObjectWindows для C + +. К., 1993., 208 С.
8. Том Сван. Програмування для Windows в Borland C + +. М., 480 С.
9. Н. Барканаті. Програмування ігор для Windows на Borland C + +. М., 1994. 512 С.
Скорочений лістинг програми і опис алгоритму
ОСНОВНІ КЛАСИголовний клас віконного інтерфейсу - TCheckersWindow
головний думаючий, що грає клас - BOARD
КОРОТКИЙ ОПИС АЛГОРИТМУ
УПРАВЛІННЯ проводиться через віконний інтерфейсний клас TCheckersWindow.
Хід людини починається натисканням лівої кнопки мишки над фішкою (при цьому запускається
функція WMLButtonDown () з класу TCheckersWindow), далі не відпускаючи кнопку курсор
пересувається на нову позицію фішки і кнопка відпускається (при цьому запускається
функція WMLButtonUp () з класу TCheckersWindow). Розглянемо роботу цих двох
функцій докладніше (див. примітки в тексті функції):
Функція WMLButtonDown ():
void TCheckersWindow:: WMLButtonDown (TMessage &) / / ===== ПОЧИНАЄМО ХІД ======
{
POINT Point;
if (WhoseTurn == Black) / / ===== перевіряє, чи дійсно ХОДИТЬ ЛЮДИНА =====
return;
SetCapture (HWindow);
GetCursorPos (& Point);
ScreenToClient (HWindow, & Point);
MoveStartPoint = bd-> GetValidSquare (Point, WhoseTurn);
if (MoveStartPoint. x)
{
MovingPieceType = bd-> GetPieceType (MoveStartPoint);
HDC hDC = GetDC (HWindow);
bd-> ClearSquare (hDC, MoveStartPoint);
HoldingPiece = TRUE;
ReleaseDC (HWindow, hDC);
}
}
Функція WMLButtonUp ():
void TCheckersWindow:: WMLButtonUp (TMessage &)
{
POINT Point;
ReleaseCapture ();
if (! HoldingPiece | | WhoseTurn == Black)
return;
GetCursorPos (& Point);
ScreenToClient (HWindow, & Point);
MoveEndPoint = bd-> GetEmptySquare (Point);
HDC hDC = GetDC (HWindow);
if (MoveEndPoint. x & & bd-> UserMove (MoveStartPoint, MoveEndPoint))
{/ / ==== ЯКЩО ЛЮДИНА МОЖЕ СЮДИ ПОСТАВИТИ ФІШКИ ... =====
bd-> RedrawBoard (hDC); / / ========= ТО Перемальовує ДОШКУ =======
EnableMenuItem (hMenu, CM_UNDO, MF_BYCOMMAND | MF_ENABLED);
EnableMenuItem (hMenu, CM_REDO, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
if (! bd-> AnotherJump ()) / / ===== МОЖНА ЗРОБИТИ ПОВТОРНИЙ ХІД? ========
{
if (bd-> NoMoreBlack ()) / / ==== ЯКЩО БІЛЬШЕ НЕОСТАЛОСЬ фішок КОМП'ЮТЕРА ... . ===
{
if (GetApplication () -> ExecDialog (new TEndDialog (this, "UserWonDlg")) / / ТО ЛЮДИНА ВИГРАВ!
== IDYES)
{
PostMessage (HWindow, WM_COMMAND, CM_FILENEW, 0L);
ReleaseDC (HWindow, hDC);
return;
}
else
{
PostMessage (HWindow, WM_COMMAND, CM_EXIT, 0L);
ReleaseDC (HWindow, hDC);
return;
}
}
PostMessage (HWindow, WM_COMMAND, CM_MOVE, 0L); / / == Перемикати НА ХІД ===
} / / ======= КОМП'ЮТЕРА =======
else / / НЕЯВНИХ ВИКЛИК ФУНКЦІЇ
; / / ComputersMove ()
}
else
{
bd-> DrawPiece (hDC, MovingPieceType, MoveStartPoint);
}
HoldingPiece = FALSE;
ReleaseDC (HWindow, hDC);
}
Функція ComputersMove ():
void TCheckersWindow:: ComputersMove (RTMessage)
{
bd-> EndUsersTime ();
WhoseTurn = Black;
EnableMenuItem (hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem (hMenu, 1, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem (hMenu, 3, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
ModifyMenu (hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_STOP, "& Stop");
DrawMenuBar (HWindow);
bd-> ComputersTurn (); / / ======= перемикається на роботу ІІ ========
HDC hDC = GetDC (HWindow);
bd-> RedrawBoard (hDC);
ReleaseDC (HWindow, hDC);
WhoseTurn = Red;
POINT CursorPoint;
GetCursorPos (& CursorPoint);
ScreenToClient (HWindow, & CursorPoint);
# Pragma warn - stv
if (PtInRect (& MainWndRect, CursorPoint))
/ * SetCursor (CursorHand) * /;
# Pragma warn + stv
ModifyMenu (hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_MOVE, "move you");
EnableMenuItem (hMenu, 0, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem (hMenu, 1, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem (hMenu, 3, MF_BYPOSITION | MF_ENABLED);
DrawMenuBar (HWindow);
if (bd-> NoMoreRed ()) / / ==== ЯКЩО БІЛЬШЕ НЕОСТАЛОСЬ фішок ЛЮДИНИ ... . ===
{
if (GetApplication () -> ExecDialog (new TEndDialog (this, "GameWonDlg")) / / === ТО КОМП'ЮТЕР ===
== IDYES) / / ====== ВИГРАВ ======
{
PostMessage (HWindow, WM_COMMAND, CM_FILENEW, 0L);
return;
}
else
{
PostMessage (HWindow, WM_COMMAND, CM_EXIT, 0L);
return;
}
}
bd-> StartUsersTime (); / / ====== ХІД ЛЮДИНИ ========
}
компоненти штучного інтелекту (ІІ)
Компоненти ШІ викликаються функцією ComputersTurn () з класу BOARD:BOOL BOARD:: ComputersTurn ()
{
int iter, i, val, row = 0, col = 0;
double t;
time_t itime1, itime2;
long lNodes;
int alpha = - MAXINT, beta = MAXINT;
StopSearch = FALSE;
ClearRedoStack ();
memcpy (SavedBoard, Board, sizeof (Board));
if (! OnlyOneMove (Black, & row, col &))
{
Nodes = 0;
time (& start_t);
PreEvaluate (); / / ======= ПОЛІТИКА ІГРИ (нападають або відбивають) =====
/ * Clear out the best-variation table * /
for (i = 0; i <= MAXPLY; + + i)
{
BestVar [i] [i]. org. SetRow (0);
BestVar [0] [i]. org. SetRow (0);
}
/ * Clear out the Killer table * /
for (i = 0; i <= MAXPLY; + + i)
{
Killer [i] [0]. org. SetRow (0);
Killer [i] [0]. Value = - 1;
}
for (iter = IterFlag? 1: SearchDepth; iter <= SearchDepth; + + iter)
{
lNodes = Nodes;
time (& itime1);
val = Evaluate (alpha, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
if (val> = beta)
{
val = Evaluate (alpha, MAXINT, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
else
{
if (val <= alpha)
{
val = Evaluate (- MAXINT, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
}
alpha = val - 12;
beta = val + 12;
/ * Seed the killer table with the best variation * /
for (i = 0; BestVar [0] [i]. org. GetRow (); + + i)
{
memcpy (& Killer [i] [0], & BestVar [0] [i], sizeof (MOVE));
Killer [i] [0]. Value = 1;
/ * Eliminate the other killer move * /
Killer [i] [1]. Value = - 1;
Killer [i] [1]. org. SetRow (0);
}
/ * Clear the rest of the killer table * /
do
{
Killer [i] [0]. org. SetRow (0);
Killer [i] [1]. org. SetRow (0);
}
while (i + + <MAXPLY);
time (& itime2);
t = difftime (itime2, itime1);
DisplaySearchStats (iter, val, Nodes - lNodes, t);
}
time (& end_t);
if ((t = difftime (end_t, start_t))! = 0)
{
sprintf (buf, "% .0 f", t);
sprintf (buf, "% ld", Nodes);
ComputerTotalTime + = t;
}
else
{
sprintf (buf, "% ld", Nodes);
}
for (i = 0; Man [Board [BestVar [0] [i]. org. GetRow ()]
[BestVar [0] [i]. org. GetCol ()]. What]. GetSide () == Black; + + i)
{
MakeActualMove (BestVar [0] [i]);
}
}
TimeToStr (buf, ComputerTotalTime);
return (TRUE);
}
Функція PreEvaluate () розробляє політику гри:
void BOARD:: PreEvaluate ()
{
int i, j, xman, inside;
int tBSizeDiv2 = BoardSize>> 1; / / (BoardSize / 2)
/************************************************* ********
This code gets a rough idea as to who is ahead in Material.
************************************************** ********/
Material [Red] = 0;
Material [Black] = 0;
Man [REDMAN]. SetValue (100);
Man [BLACKMAN]. SetValue (100);
Man [REDKING]. SetValue (140);
Man [BLACKKING]. SetValue (140);
Man [EMPTY]. SetValue (0);
Man [OFFBOARD]. SetValue (0);
for (i = 1; i <= BoardSize; + + i)
{
for (j = 1; j <= BoardSize; + + j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide ()] + = Man [xman]. GetValue ();
}
}
/************************************************* ***
Now adjust the Material weights based on who is ahead.
This is to encourage the fellow who is winning to exchange pieces
and the fellow who is behind to not exchange pieces.
If Material is dead even then you shouldn't try to force exchanges
just on general principles.
************************************************** *** /
if (Material [Red]> = Material [Black])
{
--Man [REDMAN];
- Man [REDKING];
}
else
{
--Man [BLACKMAN];
- Man [BLACKKING];
}
/************************************************* ***
Examine each and every square and calculate the bonus values.
************************************************** *** /
for (i = 1; i <= BoardSize; + + i)
{
for (j = 1; j <= BoardSize; + + j)
{
inside = (j> 1 & & j <BoardSize)? 1: 0;
SValue [i] [j] [REDMAN] = Man [REDMAN]. GetValue () + inside;
SValue [i] [j] [REDKING] = Man [REDKING]. GetValue () + inside;
SValue [i] [j] [BLACKMAN] = Man [BLACKMAN]. GetValue () + inside;
SValue [i] [j] [BLACKKING] = Man [BLACKKING]. GetValue () + inside;
/ * Bonus points for central squares * /
if (abs (tBSizeDiv2 - i) <2 & & abs (tBSizeDiv2 - j) <3)
{
+ + SValue [i] [j] [REDMAN];
+ + SValue [i] [j] [REDKING];
+ + SValue [i] [j] [BLACKMAN];
+ + SValue [i] [j] [BLACKKING];
}
/ * Bonus for non-Crown piece advancement * /
if (i> 2)
{
SValue [i] [j] [REDMAN] + = i - 2;
}
if (i <BoardSize - 2)
{
SValue [i] [j] [BLACKMAN] + = BoardSize - i - 1;
}
if (i == 1)
+ + SValue [i] [j] [REDMAN];
if (i == BoardSize)
+ + SValue [i] [j] [BLACKMAN];
}
}
Material [Red] = 0;
Material [Black] = 0;
for (i = 1; i <= BoardSize; + + i)
{
for (j = 1; j <= BoardSize; + + j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide ()] + = SValue [i] [j] [xman];
}
}
}
Функція Evaluate () представляє безпосередньо функцію ШІ. Основний принцип -
на глибину depth анадблжлізіруются можливі ходи комп'ютера і ходи у людини - шукаємо найкращу стратегію:
int BOARD:: Evaluate (int alpha, int beta, SIDE player, int row, int col, int limit, int ply)
{
MOVE * list = new MOVE [MAXMOVES];
MOVE * mptr, * endptr;
int NumMoves, val;
int num_back = 0;
int retval = 0;
int t1 = WIN - 2 - ply;
int plyp1 = ply + 1;
if (StopSearch)
goto END_EVALUATE;
+ + Nodes;
if ((NumMoves = Lmg (list, player, row, col, ply)) == 0)
{
retval = LOSS + ply;
goto END_EVALUATE;
}
MessageScan ();
if (StopSearch)
{
retval = 0;
goto END_EVALUATE;
}
if (list-> Quiescent (limit, NumMoves, ply))
{
retval = (Material [player] - Material [OPLAYER] + (NumMoves> 3? 1: 0));
goto END_EVALUATE;
}
for (mptr = list, endptr = mptr + NumMoves; mptr <endptr & & alpha <t1; mptr + +)
{
MakeMove (* mptr);
if (mptr-> Capture! = EMPTY)
{
if (! (mptr-> Crown) & & CanJump (player, mptr-> dest. GetRow (), mptr-> dest. GetCol ()))
{
val = Evaluate (alpha, beta, player, mptr-> dest. GetRow (), mptr-> dest. GetCol (), limit, plyp1);
}
else
{
val = Evaluate (- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
}
else
{
if (limit == 0 | | NumMoves == 1)
{
val = Evaluate (- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
else
{
val = Evaluate (- beta, - alpha, OPLAYER, 0, 0, limit? limit - 1: 0, plyp1) * - 1;
}
}
UnMakeMove (* mptr);
if (val> alpha)
{
if (val> = beta)
{
if (KillerFlag)
UpdateKillerTable (* mptr, ply);
retval = beta;
goto END_EVALUATE;
}
else
{
alpha = val;
+ + Num_back;
UpdateBestVariation (mptr, ply);
}
}
BestVar [plyp1] [plyp1]. org. SetRow (0);
}
retval = alpha;
END_EVALUATE:
delete list;
return retval;
}
Допоміжна функція GenMoves () генерурует можливі ходи і
записує їх у список:
/********************************************
generates the list of moves for a given player at a row, col
returns the number of legal moves found
********************************************/
int BOARD:: GenMoves (MOVE * list, int row, int col)
{
int NumMoves;
int what;
int trow1 = row + 1, tcol1 = col + 1, trowm1 = row - 1, tcolm1 = col - 1;
NumMoves = 0;
what = Board [row] [col]. What;
if (what == REDKING | | what == BLACKKING | | what == BLACKMAN)
{
if (Board [trowm1] [tcolm1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trowm1);
list-> dest. SetCol (tcolm1);
list-> Capture = EMPTY;
list-> Crown = ((row == 2) & & (what == BLACKMAN));
+ + NumMoves;
+ + List;
}
if (Board [trowm1] [tcol1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trowm1);
list-> dest. SetCol (tcol1);
list-> Capture = EMPTY;
list-> Crown = ((row == 2) & & (what == BLACKMAN));
+ + NumMoves;
+ + List;
}
}
if (what == REDKING | | what == BLACKKING | | what == REDMAN)
{
if (Board [trow1] [tcolm1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trow1);
list-> dest. SetCol (tcolm1);
list-> Capture = EMPTY;
list-> Crown = ((row == BoardSize - 1) & & (what == REDMAN));
+ + NumMoves;
+ + List;
}
if (Board [trow1] [tcol1]. What == EMPTY)
{
list-> org. SetRow (row);
list-> org. SetCol (col);
list-> dest. SetRow (trow1);
list-> dest. SetCol (tcol1);
list-> Capture = EMPTY;
list-> Crown = ((row == BoardSize - 1) & & (what == REDMAN));
+ + NumMoves;
+ + List;
}
}
return (NumMoves);
}
Опис роботи програми
Гра запускається файлом CHECKERS. EXE. Внаслідок того, що програма компілювалися в пакеті BORLAND C + + 3.1. для WINDOWS, для запуску програми необхідні такі DLL - файли:BC30RTL. DLL
OWL31. DLL
TCLASS31. DLL
У текстовому файлі DEPTH зберігається єдина настройка гри - глибина аналізу ходів, за умовчанням вона встановлена в 3 - середній рівень гри в шашки.
Меню гри напрочуд проста і складається з єдиного пункту - "move you" - пропуск ходу.
Нижче наведено два екранні копії програми.
Початок гри
Висновки
В ході курсової роботи було досліджено джерела з завданням штучного інтелекту (ШІ), розглянуто вже існуючі програми для шашкових ігор.Була розроблена відносно нескладна функція ШІ, головними завданнями якої є передбачення на встановлену глибину своїх ходів і ходів противника. Це пророцтво базується на виборі найкращих ходів з обох сторін. На фінальному етапі функція ШІ обирає найбільш вигідну для комп'ютера ланцюжок ходів.
Програма відрізняється від існуючих на ринку простотою інтерфейсу і налаштувань.
Література
1. http:// newasp. omskreg. ru / intellect2. Касаткін А.І., Вальвачев О.М. Професійне програмування на мові Сі. Мн., 1992. 240 С.
3. Нейбауер О. Моя перша програма на С / С + +. П., 1995. 368 С.
4. Бруно Бабе. Просто і ясно про Borland C + +. М., 1996. 400 С.
5. Шамас Н.К. Основи С + + і об'єктно-орієнтованого програмування. К., 1996. 448 С.
6. Довідник по класах Borland C + + 4.0.К., 1994.256 С.
7. ObjectWindows для C + +. К., 1993., 208 С.
8. Том Сван. Програмування для Windows в Borland C + +. М., 480 С.
9. Н. Барканаті. Програмування ігор для Windows на Borland C + +. М., 1994. 512 С.